package skewreduce.lib;

import java.util.ArrayList;
import java.util.Arrays;

public final class SparseArrayRef<T> implements SparseArray<T> {
	final int limit;
	ArrayList<T> data;
	int[]        indexes;
	int          numElem;
	
	public SparseArrayRef(int capacity) {
		this.limit = capacity;
		if ( capacity < 64 ) {
			data = new ArrayList<T>(limit);
			for ( int i = 0; i < limit; ++i )
				data.add(null);
		} else {
			indexes = new int[ ((capacity-1) << 1 )/3];
			data = new ArrayList<T>();
		}
	}
	
	@Override
	public T get(int i) {
		if ( indexes == null ) {
			return data.get(i);
		} else {
			int k = Arrays.binarySearch(indexes, 0, numElem, i);
			if ( k < 0 ) return null; // does not exists
			return data.get(k);
		}
	}
	
	@Override
	public T set(int i,T item) {
		if ( indexes == null ) {
			T old = data.get(i);
			data.set(i,item);
			return old;
		} else {
			int k = Arrays.binarySearch(indexes, 0, numElem, i);
			if ( k < 0 ) {
				// have to insert manually
				if ( numElem < indexes.length ) {
					// do sparse mode
					// update indexes
					k = -1 * (k + 1);
					System.arraycopy(indexes, k, indexes, k+1, numElem - k);
					indexes[k] = i;
					// update list
					data.add(k,item);
				} else {
					// we hit the limit. convert to dense mode
					ArrayList<T> newData = new ArrayList<T>(limit);
					for ( int x = 0; x < limit; ++x )
						newData.add(null);
					int x = 0;
					for ( T d : data ) {
						newData.set(indexes[x++],d);
					}
					indexes = null;
					data = newData;
					k = i;
				}
				++numElem;
			}
			return data.get(k);
		}
	}
	
	public int size() { return numElem; }

	@Override
	public int dimension() {
		return limit;
	}
	
}
